package me.timlong.simulation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class YanghuiTriangle {


    /**
     * 题目描述
     * 给出一个索引k，返回杨辉三角的第k行
     * 例如，k=3，
     * 返回[1,3,3,1].
     * 备注：
     * 你能将你的算法优化到只使用O(k)的额外空间吗?
     */
    public ArrayList<Integer> getRow(int rowIndex) {


        if(rowIndex < 0)
            return null;

        if(0 == rowIndex){
            ArrayList<Integer> rowIndex_res = new ArrayList<>();
            rowIndex_res.add(1);
            return rowIndex_res;
        }


        // 下标为0的元素为哨兵元素
        int[] rowOfYanghui = new int[rowIndex + 2];
        rowOfYanghui[1] = 1;
        rowOfYanghui[0] = 1;

        // 外层层数循环从第一层开始循环
        for (int i = 1; i <= rowIndex ; i++) {
            // 层次内部数字的确定
            rowOfYanghui[i + 1] = 1;

            // 这里使用一个哨兵元素rowOfYanghui[0]保存被覆盖的rowOfYanghui[j]
            for (int j = 2; j <= i ; j++) {
                rowOfYanghui[j] = rowOfYanghui[0] + rowOfYanghui[j];
                rowOfYanghui[0] = rowOfYanghui[j] - rowOfYanghui[0];
            }
        }
        List<Integer> rowIndex_res = IntStream.of(rowOfYanghui).boxed().collect(Collectors.toList());
        rowIndex_res.remove(0);

        return (ArrayList<Integer>) rowIndex_res;
    }

    public static void main(String[] args) {

        ArrayList<Integer> res = new YanghuiTriangle().getRow(5);
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }


    }


}
